package leetcode.editor.cn;

import java.util.*;
import leetcode.editor.common.*;

public class PalindromeLinkedList {

    //leetcode submit region begin(Prohibit modification and deletion)
    /**
     * Definition for singly-linked list.
     * public class ListNode {
     *     int val;
     *     ListNode next;
     *     ListNode() {}
     *     ListNode(int val) { this.val = val; }
     *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     * }
     */
    class Solution {

        // 1. 快慢指针找到中间节点，然后翻转后半部分链表
        public boolean isPalindrome(ListNode head) {
           if(head==null){
               return false;
           }


            final List<Integer> list = new ArrayList<>();
            while (head!=null){
                list.add(head.val);
                head = head.next;
            }

             // 双指针
            int front =0;

            int back = list.size()-1;

            while (front<back){
                if(!list.get(front).equals(list.get(back))){
                    return false;
                }
                front++;
                back--;

            }

           /* final int size = list.size();

            for (int i = 0; i < size/2; i++) {
                if(!list.get(i).equals(list.get(size-i-1))){
                    return false;
                }
            }*/


            return true;
        }

        // 2. 快慢指针找到中间节点，然后翻转后半部分链表
        public boolean isPalindrome2(ListNode head) {
            ListNode slow = head;
            ListNode fast = head;

            // 找到中间节点
            while (fast != null && fast.next != null) {
                slow = slow.next;
                fast = fast.next.next;
            }

            // 链表为偶数，需要再前进一步
            while (fast != null) {
                slow = slow.next;
            }




            return false;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

    
    public static void main(String[] args) {
        Solution solution = new PalindromeLinkedList().new Solution();
        // put your test code here
        
    }
}
